package org.kfive.nova.algorithm.binarytree;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 14-5-14
 * Time: 下午4:01
 * To change this template use File | Settings | File Templates.
 */
public class BinaryTree {

    private BinaryTree root;

    public BinaryTree getRoot(){
        return  this.root;
    }

    public void setRoot(BinaryTree root){
        this.root = root;
    }

    public BinaryTreeNode ConstructTree(int [] preorder,int []inorder){
        if(preorder!=null&&preorder.length>0&&inorder!=null&&inorder.length>0){
            return ConstructTreeCore(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        }else {
            return null;
        }
    }

    public BinaryTreeNode ConstructTreeCore(int [] preorder,int []inorder,int prestart,int preend,int instart,int inend){
        BinaryTreeNode treeRoot = new BinaryTreeNode();
        treeRoot.setNodeValue(preorder[prestart]);
        if(prestart<preend&&instart<inend){
            int j=0;
            for(int i:inorder){
                if(i==treeRoot.getNodeValue()){
                    break;
                }
                j++;
            }
            int ltreelength = j-instart;
            if(ltreelength>0){
                treeRoot.setlTreeNode(ConstructTreeCore(preorder,inorder,prestart+1,j,instart,j));
            }
            if(ltreelength<(preend-prestart)){
                treeRoot.setrTreeNode(ConstructTreeCore(preorder,inorder,prestart+ltreelength+1,preend,j,inend));
            }
        }
        return treeRoot;
    }
}
